package 中等.贪心思想;

/**
 * 给你一个正整数数组 arr（可能存在重复的元素），请你返回可在 一次交换
 * （交换两数字 arr[i] 和 arr[j] 的位置）后得到的、按字典序排列小于
 * arr 的最大排列。
 * 如果无法这么操作，就请返回原数组。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/previous-permutation-with-one-swap
 */
public class 交换一次的先前排列_1053 {

    public static void main(String[] args) {

    }

    /**
     * 贪心思想
     * 得到的数组字典序要小于原数组，也就是说交换之后第
     * 1个位置减小，第2个位置增加，想要使得到的数组
     * 字典序尽可能大，那么第一个位置尽可能靠后，且位置
     * 所在的元素值尽可能大
     * 步骤：从右边开始找，找到第一个其右边存在比它小的数字
     * 取右边比它小的最大数字进行交换
     */
    public int[] prevPermOpt1(int[] arr) {
        for (int i = arr.length - 2; i >= 0; i--) {
            int replaceIdx = -1;

            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[i]) {
                    if (replaceIdx == -1 || arr[j] > arr[replaceIdx]) {
                        replaceIdx = j;
                    }
                }
            }

            if (replaceIdx != -1) {
                int temp = arr[i];
                arr[i] = arr[replaceIdx];
                arr[replaceIdx] = temp;
                return arr;
            }
        }

        return arr;
    }

}
